package com.bow.algorithm.structure;

import java.util.PriorityQueue;

/**
 * 构建hufManTree<br/>
 * 选出最小的两个相加得和值，然后再比较。<br/>
 * 在权为w1,w2,…,wn的n个叶子结点的所有二叉树中，带权路径长度WPL最小的二叉树称为赫夫曼树或最优二叉树。<br/>
 * https://www.jianshu.com/p/b9352dd3f406 <br/>
 *
 * <pre>
 *     AAAAAAABBCCCCCDDDD
 * a.  A7  B2 C5 D4
 * b.  7  5  6
 *          / \
 *         B2  D4
 * c.  7    11
 *         / \
 *        C5  6
 *           / \
 *          B2  D4
 *
 * d.       18
 *         / \
 *        A7  11
 *           / \
 *          C5  6
 *             / \
 *           B2  D4
 *
 * 字典： A--0  B--110 C--10 D--111
 * 哈夫曼树就是一个字典，他能确保频率越高的字符用的bit数最少。有了这个字典就可以编解码了。
 * AAAAAAABBCCCCCDDDD --> 0000000 110110 1010101010 111111111111
 * 在解码时，如果从哈夫曼树中找到对应的字符了说明找到叶子节点了，这些bit就对应到了一个值。
 * </pre>
 * 
 * @param <T>
 */
public class HufManTree<T> {

	public HufManNode<T> makeTree(T[] chars, int[] freq) {
		if (chars == null || freq == null || chars.length == 0 || freq.length == 0 || chars.length != freq.length) {
			return null;
		}
		PriorityQueue<HufManNode<T>> pq = new PriorityQueue<HufManNode<T>>();
		for (int i = 0; i < chars.length; i++) {
			HufManNode<T> node = new HufManNode<T>(chars[i], freq[i]);
			pq.add(node);
		}
		while (pq.size() != 1) {
			HufManNode<T> node1 = pq.poll();
			HufManNode<T> node2 = pq.poll();
			HufManNode<T> merge = new HufManNode<>(node1, node2);
			pq.add(merge);
		}
		return pq.poll();
	}

	public void calCode(HufManNode<T> node, String code) {
		if (node.left == null && node.right == null) {
			node.code = code;
			System.out.println(node.value + ":" + node.code);
			return;
		}
		calCode(node.left, code + "0");
		calCode(node.right, code + "1");
	}

	private static class HufManNode<T> implements Comparable<HufManNode<T>> {
		T value;
		Integer freq;
		HufManNode<T> left = null;
		HufManNode<T> right = null;
		String code;

		public HufManNode(T value, int freq) {
			this.value = value;
			this.freq = freq;
		}

		public HufManNode(HufManNode<T> left, HufManNode<T> right) {
			this.freq = left.freq + right.freq;
			this.left = left;
			this.right = right;
		}

		@Override
		public int compareTo(HufManNode<T> o) {
			return this.freq.compareTo(o.freq);
		}
	}

	public static void main(String[] args) {
		Character[] chars = new Character[] { '7', '2', '5', '4' };
		int[] freq = new int[] { 7, 2, 5, 4 };
		HufManTree<Character> tree = new HufManTree<Character>();
		HufManNode<Character> root = tree.makeTree(chars, freq);
		tree.calCode(root, "");
	}

}
